/*有一组项目，项目需要花费一定的资金，获取利润。假设我们可以做k个项目，启动资金为m
求出一个做项目的顺序，使得最后我们的资金最多*/
#include "../util/util.h"
#include <queue>
#include <iostream>
using namespace std;
class Project
{
public:
    Project(int c, int p) : cost(c), profit(p) {}
    // 花费
    int cost;
    // 利润
    int profit;
};
// 比较谁的花费更小
class MinCostComparator
{
public:
    bool operator()(Project &a, Project &b)
    {
        if (a.cost > b.cost)
        {
            return true;
        }
        return false;
    }
};
// 比较谁的利润更大
class MaxProfitComparator
{
public:
    bool operator()(Project &a, Project &b)
    {
        if (a.profit < b.profit)
        {
            return true;
        }
        return false;
    }
};
int findMaximizedCapital(int k, int M, const int *costArr, const int *profitArr, int length)
{
    priority_queue<Project, vector<Project>, MinCostComparator> minCostQueue;
    priority_queue<Project, vector<Project>, MaxProfitComparator> maxProfitQueue;
    // 将所有项目装进小根堆(cost)
    for (int i = 0; i < length; i++)
    {
        minCostQueue.push(Project(costArr[i], profitArr[i]));
    }
    while (k--)
    {
        // 将所有现阶段能做的项目全部放进maxProfitQueue
        while (!minCostQueue.empty() && minCostQueue.top().cost <= M)
        {
            maxProfitQueue.push(minCostQueue.top());
            minCostQueue.pop();
        }
        // 判断是否有可以承担的项目
        if (maxProfitQueue.empty())
        {
            return M;
        }
        // 结算资金
        M += maxProfitQueue.top().profit;
    }
    return M;
}
int main()
{
    int costArr[10];
    int profitArr[10];
    int length = Util::GetInstance().getArrFromStdin("请输入所有项目的花费",costArr);
    Util::GetInstance().getArrFromStdin("请输入所有项目的利润",profitArr);
    int k =4;
    int m =1;
    int res = findMaximizedCapital(k,m,costArr,profitArr,length);
    cout<<"最终资金为： "<<res<<endl;

    // priority_queue<Project, vector<Project>, MinCostComparator> minCostQueue;
    // minCostQueue.push(Project(1, 3));
    // minCostQueue.push(Project(2, 4));
    // while (!minCostQueue.empty())
    // {
    //     cout << minCostQueue.top().cost << " " << minCostQueue.top().profit << endl;
    //     minCostQueue.pop();
    // }

    return 0;
}